#include "gx_lsq.h"
#include <stdlib.h>
#include <stdio.h>
#include "gx_err.h"

static inline void list_init(LIST* list)
{
	if(list == NULL)
		fatal(PARAMETER_ERROR,"list init parameter cannot be NULL");
	list->head = NULL;
	list->tail = NULL;
	list->count = 0;
}

LIST* list_new()
{
	LIST *list;
	list = (LIST*)malloc(sizeof(LIST));

	if(list == NULL)
	{
		fatal(NOMEM,"malloc error");
	}

	list_init(list);
	return list;
}
static inline NODE* alloc_node()
{
	NODE *node = (NODE*)malloc(sizeof(NODE));
	if(node == NULL)
		fatal(NOMEM,"malloc error");
	return node;
}

int list_addtail(LIST* list ,DATA data)
{
	if(list == NULL)
		return PARAMETER_ERROR;

	NODE* node = alloc_node();

	node->data = data;
	node->next=NULL;
	
	if(list->head == NULL)
	{
		list->head=list->tail=node;
		node->prev=NULL;
		list->count++;
	}
	else
	{
		node->prev = list->tail;
		list->tail->next = node;
		list->tail = node;
		list->count++;
	}

	return SUCCESS;
}

int list_addhead(LIST* list,DATA data)
{
	if(list == NULL)
		return PARAMETER_ERROR;

	NODE* node = alloc_node();

	node->data = data;
	node->prev = NULL;

	if(list->tail ==  NULL)
	{
		list->head = node;
		node->next = NULL;
		list->tail = node;
		list->count++;
	}
	else
	{
		node->next = list->head;
		list->head->prev = node;
		list->head = node;
		list->count++;
	}

	return SUCCESS;
}

void list_walk(LIST* list,WALK walk)
{
	if(walk == NULL)
		return;
	if(list == NULL)
		return;
	NODE* tmp = list->head;
	while(tmp != NULL)
	{
		walk(tmp->data);
		tmp = tmp ->next;
	}
}

void list_removeall(LIST* list,void (*list_free)(DATA data))
{
	NODE* tmp = list->head;
	while(tmp != NULL)
	{
		NODE* forfree = NULL;
		if(list_free != NULL)
		{
			list_free(tmp->data);
		}
		forfree = tmp;
		tmp = tmp->next;
		free(forfree);
	}
	list->head = NULL;
	list->tail = NULL;
	list->count = 0;
	free(list);
}

DATA list_gethead(LIST* list)
{
	if(list == NULL)
		return NULL;

	if(list->head == NULL)
		return NULL;

	return list->head->data;
}

DATA list_gettail(LIST* list)
{
	if(list == NULL)
		return NULL;
	if(list->tail == NULL)
		return NULL;
	return list->tail->data;
}

DATA list_removehead(LIST* list)
{
	if(list == NULL)
		return NULL;
	if(list->head == NULL)
		return NULL;
	DATA data = list->head->data;
	NODE *node = list->head;
	list->head = list->head->next;
	if(list->head != NULL)
	{
		list->head->prev = NULL;
	}
	else
	{
		list->tail = NULL;
	}
	list->count--;
	free(node);
	return data;
}

DATA list_removetail(LIST* list)
{
	if(list == NULL)
		return NULL;

	if(list->tail == NULL)
		return NULL;
	DATA data = list->tail->data;
	NODE *node = list->tail;
	list->tail = list->tail->prev;
	if(list->tail != NULL)
	{
		list->tail->next = NULL;
	}
	else
	{
		list->head=NULL;
	}
	list->count--;
	free(node);
	return data;
}

int list_count(LIST* list)
{
	if(list == NULL)
		return 0;
	return list->count;
}

int list_addafter(LIST* list,DATA data,DATA newdata,int(*compare)(DATA d1,DATA d2))
{
	if(list == NULL || compare == NULL)
		return PARAMETER_ERROR;
	if(data == NULL || newdata == NULL)
		return NODATA;

	NODE *node = list->head;
	while(node != NULL)
	{
		if(compare(data,node->data) == 0)
			break;
		node = node->next;
	}

	if(node == NULL)
	{
		return NODATA;
	}
	else
	{
		NODE *tmp = alloc_node();
		tmp->data = newdata;
		tmp->prev = node;
		tmp->next = node->next;

		if(node->next != NULL)
		{
			node->next->prev = tmp;
		}

		node->next = tmp;

		if(node == list->tail)
			list->tail = tmp;
		list->count++;
		return SUCCESS;
	}
}

static inline void add_before(NODE *node,NODE* tmp)
{
	tmp->next = node;
	tmp->prev = node->prev;

	if(node->prev != NULL)
	{
		node->prev->next = tmp;
	}
	node->prev = tmp;
}

int list_addbefore(LIST* list,DATA data,DATA d1,int (*compare)(DATA d1,DATA d2))
{
	if(list == NULL || compare == NULL)
		return PARAMETER_ERROR;
	if(data == NULL || d1 == NULL)
		return NODATA;

	NODE *node = list->head;

	while(node != NULL)
	{
		if(compare(data,node->data) == 0)
			break;
		node = node->next;
	}

	if(node == NULL)
	{
		return NODATA;
	}
	else
	{
		NODE *tmp = alloc_node();
		if(tmp == NULL)
			fatal(NOMEM,"malloc error");
		tmp->data = d1;
		add_before(node,tmp);
		list->count++;

		if(node == list->head)
		{
			list->head = tmp;
		}
		return SUCCESS;
	}
}

NODE* list_finddata(LIST* list,DATA data,int(*compare)(DATA d1,DATA d2))
{
	if(list == NULL || data == NULL || compare == NULL)
		return NULL;

	NODE* node = list->head;
	
	while(node != NULL)
	{
		if(compare(data,node->data) == 0)
			return node;
		node = node->next;
	}
	return NULL;
}

int list_isexist(LIST* list,DATA data,int(*compare)(DATA d1,DATA d2))
{
	if(list == NULL || data == NULL)
		return NODATA;

	if(compare == NULL)
		return PARAMETER_ERROR;

	NODE *node = list->head;

	while(node != NULL)
	{
		if(compare(data,node->data) == 0)
			return SUCCESS;
		node = node->next;
	}

	return NODATA;
}

DATA list_removedata(LIST* list,DATA data,int (*compare)(DATA d1,DATA d2))
{
	if(list == NULL || data == NULL || compare == NULL)
		return NULL;
	
	NODE *node = list_finddata(list,data,compare);

	if(node == NULL)
	{
		return NULL;
	}
	else if(node == list->head)
		return list_removehead(list);
	else if(node == list->tail)
		return list_removetail(list);
	else
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
		DATA tmp = node->data;
		list->count--;
		free(node);
		return tmp;
	}
}

DATA list_firstpos(LIST *list,NODE** node)
{
	if(list == NULL || node == NULL)
		return NULL;
	*node = list->head;
	if(*node == NULL)
		return NULL;
	else
		return (*node)->data;
}

DATA list_nextpos(LIST *list,NODE** node)
{
	if(list == NULL || node == NULL)
		return NULL;

	if(*node == NULL)
		return NULL;
	else
	{
		*node = (*node)->next;
		if(*node == NULL)
		{
			return NULL;
		}
		else
			return (*node)->data;
	}
}

int list_empty(LIST* list)
{
	if(list == NULL)
		return PARAMETER_ERROR;
	else
	{
		return list->count==0;
	}
}

STACK* stack_new()
{
	return list_new();
}

int stack_push(STACK* stack,DATA data)
{
	return list_addhead(stack,data);
}

DATA stack_pop(STACK* stack)
{
	return list_removehead(stack);
}

int stack_empty(STACK* stack)
{
	return list_empty(stack);
}

void stack_freeall(STACK* stack,void(*free)(void*))
{
	list_removeall(stack,free);
}

int  stack_count(STACK* stack)
{
	return list_count(stack);
}

QUEUE* queue_new()
{
	return list_new();
}

int queue_in(QUEUE* queue,DATA data)
{
	return list_addtail(queue,data);
}

DATA queue_out(QUEUE* queue)
{
	return list_removehead(queue);
}

int  queue_empty(QUEUE* queue)
{
	return list_empty(queue);
}

void queue_freeall(QUEUE* queue,void(*free)(void*))
{
	return list_removeall(queue,free);
}

int queue_count(QUEUE* queue)
{
	return list_count(queue);
}

static inline LTSEQ* alloc_seqnode()
{
	LTSEQ* list = (LTSEQ*)malloc(sizeof(LTSEQ));
	if(list == NULL)
		fatal(NOMEM,"malloc error");
	return list;
}

LTSEQ* ltseq_new(int(*compare)(DATA d1,DATA d2))
{
	if(compare == NULL)
		fatal(PARAMETER_ERROR,"funcution can not be NULL!");

	LTSEQ* lsq = alloc_seqnode();
	lsq->compare = compare;
	list_init((LIST*)lsq);
	return lsq;
}

int ltseq_add(LTSEQ* lsq,DATA data)
{
	if(list_count((LIST*)lsq) == 0)
	{
		list_addhead((LIST*)lsq,data);
		return SUCCESS;
	}

	if(lsq->compare(lsq->head->data,data) >= 0)
	{
		list_addhead((LIST*)lsq,data);
	}
	else if(lsq->compare(lsq->tail->data,data) <= 0)
	{
		list_addtail((LIST*)lsq,data);
	}
	else
	{
		NODE* node = lsq->head->next;
		while(node != NULL && lsq->compare(node->data,data) < 0 )
			node = node->next;

		if(node == NULL)
		{
			fatal(NODATA,"list error!");
		}

		NODE *tmp = alloc_node();
		tmp->data = data;
		add_before(node,tmp);
		lsq->count++;
		if(node == lsq->head)
		{
			lsq->head = tmp;
		}
	}
	return SUCCESS;
}

NODE* ltseq_finddata(LTSEQ* ltq,DATA data)
{
	if(ltq == NULL || data == NULL)
		return NULL;

	if(list_count((LIST*)ltq) == 0)
		return NULL;

	int result = ltq->compare(ltq->tail->data,data);

	if(result == 0)
		return ltq->tail;
	else if(result < 0)
		return NULL;

	NODE *node = ltq->head;

	while(node != NULL)
	{
		int result = ltq->compare(node->data,data);
		if(result == 0)
			return node;
		else if(result > 0)
			return NULL;
		node = node->next;
	}

	return NULL;
}
